/**
 * 79. Word Search 单词搜索
 * https://leetcode.com/problems/word-search/description/
 */
class WordSearch {
    private static final int[][] DIRS = {{0, -1},{0, 1},{-1, 0},{1, 0}};

    /**
     * 方法：exist - 在二维字符数组中查找是否存在指定的单词
     * Args:
     *   board: char[][] - 二维字符数组，表示字母板
     *   word: String - 要查找的单词
     * Returns:
     *   boolean - 如果找到单词返回true，否则返回false
     * Time: O(M*N*3^L) - 其中M和N是board的行列数，L是word的长度，
     * 除了递归入口，其余递归至多有 3 个分支（因为至少有一个方向是之前走过的），所以每次递归（回溯）的时间复杂度为 O(3^L)，
     * 一共回溯 O(MN) 次，所以时间复杂度为 O(M*N*3^L）
     * Space: O(L) - 递归调用栈的深度最多为L
     */
    public boolean exist(char[][] board, String word) {
        // 为了方便，直接用数组代替哈希表
        int[] cnt = new int[128];
        for(char[] row: board){
            for(char c : row){
                cnt[c]++;
            }
        }

        char[] w = word.toCharArray();
        int[] wordCnt = new int[128];
        for(char c : w){
            if(++wordCnt[c] > cnt[c]){
                return false;
            }
        }
        if(cnt[w[w.length-1]] < cnt[w[0]]){
            w = new StringBuilder(word).reverse().toString().toCharArray();
        }

        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(backtrack(i, j, 0, board, w)){
                    return true;
                }
            }
        }
        return false;
    }

    private boolean backtrack(int i , int j, int k, char[][] board, char[] word){
        if (board[i][j] != word[k]){
            return false;
        }
        if(k == word.length - 1){
            return true;
        }
        board[i][j] = 0;
        for(int[] d: DIRS){
            int x = i + d[0];
            int y = j + d[1];
            if(0 <= x && x< board.length && 0 <= y && y<board[x].length && backtrack(x, y , k+1, board, word)){
                return true;// 搜到了！
            }
        }
        board[i][j] = word[k];
        // 恢复现场
        return false;
    }
}